package linkedList;

import java.util.Stack;

//单向链表 按照编号顺序插入
public class SingleLinkedListDemo2 {
    public static void main(String[] args) {
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");
        //创建一个链表
        SingleLinkedList2 singleLinkedList2 = new SingleLinkedList2();
        singleLinkedList2.add2(heroNode1);
        singleLinkedList2.add2(heroNode2);
        singleLinkedList2.add2(heroNode3);
        singleLinkedList2.add2(heroNode4);
        singleLinkedList2.list();
//        singleLinkedList2.update(new HeroNode(4, "马大师", "耗子尾汁"));
//        System.out.println("修改后");
//        singleLinkedList2.list();
//        System.out.println("删除后");
//        singleLinkedList2.delete(3);
//        singleLinkedList2.list();
//        System.out.println(getLength(singleLinkedList2.getHead()));
//
//        HeroNode lastIndexNode = findLastIndexNode(singleLinkedList2.getHead(), 3);
//        System.out.println(lastIndexNode);

//        reversList(singleLinkedList2.getHead());

        reversPrint(singleLinkedList2.getHead());
    }

    /**
     * 反向打印链表
     */
    public static void reversPrint(HeroNode head) {
        System.out.println("反向打印");
        if (head.next == null) {
            return;
        }
        Stack<HeroNode> stack = new Stack<>();
        HeroNode temp = head.next;
        while (temp != null) {
            stack.add(temp);
            temp = temp.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }


    /**
     * 反转链表
     */
    public static void reversList(HeroNode head) {
        if (head.next == null || head.next.next == null) {
            return;
        }
        HeroNode reversNode = head;
        HeroNode next = head.next;
        HeroNode temp = null;
        while (next != null) {
            temp = next.next;
            next.next = reversNode.next; //将节点的尾部指向新节点的头部的后面
            reversNode.next = next;     //将新节点的后一个指向当前节点
            next = temp; //后移
        }

        System.out.println("反转后");
        System.out.println(reversNode);
        System.out.println(reversNode.next);
        System.out.println(reversNode.next.next);
        System.out.println(reversNode.next.next.next);
        System.out.println(reversNode.next.next.next.next);
    }

    /**
     * 查找单链表中倒数的第k个节点
     */
    public static HeroNode findLastIndexNode(HeroNode head, int index) {
        if (head.next == null) {
            return null;
        }
        HeroNode temp = head.next;
        int length = getLength(head); //获取链表长度
        for (int i = 0; i < length - index; i++) {  //长度-index就是倒是第k个
            temp = temp.next;
        }
        return temp;
    }

    //获取单链表节点的个数

    /**
     * @param head 链表头节点
     * @return 返回链表的有效个数
     */
    public static int getLength(HeroNode head) {
        if (head.next == null) {
            return 0;
        }
        int lenth = 0;
        HeroNode temp = head;
        while (temp.next != null) {
            lenth++;
            temp = temp.next;
        }
        return lenth;
    }

}

//SingleLinkedList
class SingleLinkedList2 {

    public HeroNode getHead() {
        return head;
    }

    //初始化一个头结点 不存放数据
    private HeroNode head = new HeroNode(0, "", "");

    //第二种方式在添加英雄时根据排名将英雄插入指定位置 如果有这个排名则添加失败 并给出提示
    public void add2(HeroNode heroNode) {
        //辅助节点
        HeroNode temp = head;
        boolean flag = false; //标志添加的编号是否存在
        while (true) {
            //找到最后
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > heroNode.no) { //位置找到，就在temp的后面插入
                break;
            } else if (temp.next.no == heroNode.no) { //说明编号存在
                flag = true;
                break;
            }
            //后移
            temp = temp.next;
        }
        if (flag) { //true不能添加
            System.out.printf("准备插入的英雄%d已经存在", heroNode.no);
        } else {
            //插入到链表中
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //更新节点
    public void update(HeroNode heroNode) {
        //辅助节点
        HeroNode temp = head;
        boolean flag = false; //标志
        while (true) {
            //找到最后
            if (temp.next == null) {
                System.out.println("未找到");
                break;
            } else if (temp.next.no == heroNode.no) { //说明编号存在
                flag = true;
                break;
            }
            //后移
            temp = temp.next;
        }
        if (flag) { //true表示找到节点
            temp.next.name = heroNode.name;
            temp.next.nickname = heroNode.nickname;
        }
    }

    //删除节点
    public void delete(int no) {
        //辅助节点
        HeroNode temp = head;
        boolean flag = false; //标志
        while (true) {
            //找到最后
            if (temp.next == null) {
                System.out.println("未找到");
                break;
            } else if (temp.next.no == no) { //说明编号存在
                flag = true;
                break;
            }
            //后移
            temp = temp.next;
        }
        if (flag) { //true表示找到节点
            temp.next = temp.next.next;
        }
    }

    //显示链表
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head;
        while (true) {
            //找到最后
            System.out.println(temp);
            //后移
            if (temp.next == null) {
                break;
            }
            temp = temp.next;

        }

    }
}
